package 面试v1.字节;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.List;

public class LeetCode802 {

    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        List<Integer> ans = new ArrayList<Integer>();
        //遍历查看每个节点
        for (int i = 0; i < n; ++i) {
            if (safe(graph, color, i)) {
                ans.add(i);
            }
        }
        return ans;
    }

    //三个状态 三级缓存
//    白色（用 00 表示）：该节点尚未被访问；
//    灰色（用 11 表示）：该节点位于递归栈中，或者在某个环上；
//    黑色（用 22 表示）：该节点搜索完毕，是一个安全节点。
    public boolean safe(int[][] graph, int[] color, int x) {
        if (color[x] > 0) {
            return color[x] == 2;//存在环
        }
        color[x] = 1;//标记中
        for (int y : graph[x]) {
            if (!safe(graph, color, y)) {
                return false;
            }
        }
        color[x] = 2;//安全节点
        return true;
    }
}

class LeetCode802_1{
    //有向图成环
    public static boolean canFinish(int numCourses, int[][] prerequisites){
        int[] isVisited = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>(numCourses);
        for(int i = 0; i < numCourses; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
        }


        for(int i = 0; i < numCourses; i++){
            if(!dfsFinish(graph, i, isVisited))
                return false;
        }
        return true;
    }

    /**
     * 0表示还未访问过，1表示已经访问了(被之前的dfs访问)，-1表示有冲突(当前dfs过程中再次进入)
     */
    private static boolean dfsFinish(List<List<Integer>> graph, int visit, int[] isVisited){
        if(1 == isVisited[visit])
            return true;
        if(-1 == isVisited[visit])
            return false;
        isVisited[visit] = -1;
        for(int next : graph.get(visit)){
            if(!dfsFinish(graph, next, isVisited))
                return false;
        }
        isVisited[visit] = 1;
        return  true;
    }
}
